/*
    单调栈-上

    前置知识 : 讲解013-用数组方式实现栈(常数时间比语言自己提供的好)

    单调栈最经典的用法是解决如下问题：
    每个位置都求：
    0）当前位置的 左侧比当前位置的数字小，且距离最近的位置 在哪
    1）当前位置的 右侧比当前位置的数字小，且距离最近的位置 在哪
    或者
    每个位置都求：
    0）当前位置的 左侧比当前位置的数字大，且距离最近的位置 在哪
    1）当前位置的 右侧比当前位置的数字大，且距离最近的位置 在哪

    单调栈过程详细图解：
    1，数组无重复值的情况
    2，数组有重复值的情况

    用单调栈的方式可以做到：求解过程中，单调栈所有调整的总代价为O(n)，单次操作的均摊代价为O(1)

    注意：这是单调栈最经典的用法，可以解决很多题目，下节课将继续介绍其他的用法
    注意：单调栈可以和很多技巧交叉使用！比如：动态规划+单调栈优化，会在【扩展】课程里讲述

    ================================================

    题目1
    单调栈最经典用法的模版
    测试链接 : https://www.nowcoder.com/practice/2a2c00e7a88a498693568cef63a4b7bb

    关键！不同题目中相等值出现时的处理！用后续的题目说明！

    ================================================

    题目2
    每日温度
    给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer
    其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后
    如果气温在这之后都不会升高，请在该位置用 0 来代替。
    测试链接 : https://leetcode.cn/problems/daily-temperatures/

    ================================================

    题目3
    子数组的最小值之和
    给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
    由于答案可能很大，因此 返回答案模 10^9 + 7
    测试链接 : https://leetcode.cn/problems/sum-of-subarray-minimums/

    注意这道题答案很大，要求取模
    对取模不熟悉的同学可以看一下：讲解041-同余原理的部分，讲了为什么要取模以及怎么取模

    ================================================

    题目4
    柱状图中最大的矩形
    给定 n 个非负整数，用来表示柱状图中各个柱子的高度
    每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积
    测试链接：https://leetcode.cn/problems/largest-rectangle-in-histogram

    ================================================

    题目5
    最大矩形
    给定一个仅包含 0 和 1 、大小为 rows * cols 的二维二进制矩阵
    找出只包含 1 的最大矩形，并返回其面积
    测试链接：https://leetcode.cn/problems/maximal-rectangle/

*/